1933F - Turtle Mission Robot and the Earthquake - CodeForces Solution

/*

    M     M          A      TTTTTTT   H    H
   M M   M M        A A        T      H    H
  M   M M   M      A___A       T      H----H
 M     M     M    A     A      T      H    H
M      M      M  A       A     T      H    H

   ___    ____    ___
  /   \  |    |  /   \  |   |
      /  |    |      /  |   |
   __/   |    |   __/   �===|==
  |      |    |  |          |
  |___   |____|  |___       |


k     k   eee   r       b     eee   r                sss
k   k     e     rr      b     e     rr       oo     s   s
kkk       e     rr rrr  b     e     rr rrr  o  o     s   s
kk        eee   rr      bbbb  eee   rr      o  o      s
k   k     e     rr      b  b  e     rr      o  o    s  s
k     k   eee   rr      bbbb  eee   rr       oo      sss

*/
/*
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#pragma GCC target("avx2,fma")
*/

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define el "\n"
#define N "NO"
#define Y "YES"
#define fx(i) fixed << setprecision(i)

const ld pi = acos(-1);
const ld eps = 1e-6;
const ll oo =  1e9+7 ;
const ll  mod2 =998244353;
const ll  mod1 = 1e9 + 7;
const int lim = 111111;
using namespace std;
ll n,m,ans;
vector<vector<int>>rok,vis,vs;
bool cant(int u,int v)
{
   return (rok[(u+1)%n][v]&&rok[(u+1)%n][v+1]);
}
ll ok(int u)
{
    u=(u-vis[u][m-1]%n+n)%n;
    int o=0;
    int t=u+1;
    while(u<n-1&&!rok[u][m-1])u++,o++;
    if(u!=n-1)o=oo;
    return min(o,t);
}
void dij()
{
    queue<pair<int,int>>sp;
    sp.push({0,0});
    vis[0][0]=0;
    while(sp.size())
    {
        auto y=sp.front();
        sp.pop();
        int i=y.first;
        int j=y.second;
        bool ok1=0;
        if(j==m-1){
        ans=min(ok(i)+vis[i][j],ans);
        ok1=1;
        }
        if(cant(i,j)||vs[i][j]||ok1)
            continue;
         vs[i][j]=1;
         if(!rok[(i+1)%n][j+1]){
        sp.push({(i+1)%n,j+1});
        
        vis[(i+1)%n][j+1]=min(vis[i][j]+1,vis[(i+1)%n][j+1]);}
        if(!rok[(i+1)%n][j]&&!rok[(i+2)%n][j]){
        sp.push({(i+2)%n,j});
        vis[(i+2)%n][j]=min(vis[(i+2)%n][j],vis[i][j]+1);
        }
    }
}
void solving_problem()
{
   cin>>n>>m;ans=oo;
        rok.clear();
        vis.clear();
        vs.clear();
        rok.resize(n);
        vis.resize(n);
        vs.resize(n);
        for(int i=0; i<n; i++)
        {
            vis[i].resize(m);
            vs[i].resize(m);
            rok[i].resize(m);
            for(int j=0; j<m; j++)
            {
                cin>>rok[i][j];
                vis[i][j]=oo;
               vs[i][j]=0;
            }
        }
        dij();
        if(ans<oo)cout<<ans<<'\n';
        else cout<<-1<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int test = 1;
     cin >> test;
    while (test--)
        solving_problem();
    return 0;
}